package com.gitee.ty850454.leetcode1047;

public class Leetcode1047_3 {

    public static void main(String[] args) {
        Leetcode1047_3 leetcode1047_3 = new Leetcode1047_3();
        System.out.println(leetcode1047_3.removeDuplicates("aaaaaaaa"));
        System.out.println(leetcode1047_3.removeDuplicates("abbaca"));
        System.out.println(leetcode1047_3.removeDuplicates("aaabbasfseesfecaaa"));
    }

    public String removeDuplicates(String s) {
        char[] source = s.toCharArray();
        CharStack stack = new CharStack(s.length());
        for (char c : source) {
            if (!stack.empty() && stack.peek() == c) {
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        return stack.toString();
    }

    public static class CharStack {

        /** 栈元素数组 */
        private final char[] elements;

        /** 栈顶索引 */
        private int topIndex = -1;

        /**
         * 初始化一个栈
         *
         * @param capacity 栈容量
         */
        public CharStack(int capacity) {
            elements = new char[capacity];
        }

        /**
         * 判断栈是否为空
         *
         * @return 空栈返回true，否则返回false
         */
        boolean empty() {
            return topIndex < 0;
        }

        /**
         * 查看堆栈顶部的对象
         *
         * @return 栈顶部的对象
         */
        public char peek() {
            return elements[topIndex];
        }

        /**
         * 压栈
         *
         * @param aChar 压入的元素
         */
        public void push(char aChar) {
            elements[++topIndex] = aChar;
        }

        /**
         * 弹栈，因为本例不需要弹出的元素所以未返回弹出的元素
         */
        public void pop() {
            topIndex--;
        }

        @Override
        public String toString() {
            return new String(elements, 0, topIndex + 1);
        }
    }
}
